home *** CD-ROM | disk | FTP | other *** search
/ Aminet 15 / Aminet 15 - Nov 1996.iso / Aminet / dev / gcc / ixemsdk.lha / man / cat3 / btree.0 < prev    next >
Text File  |  1996-09-02  |  8KB  |  199 lines
  1.  
  2.  
  3.  
  4. BTREE(3)                                                 BTREE(3)
  5.  
  6.  
  7. NNAAMMEE
  8.        btree - btree database access method
  9.  
  10. SSYYNNOOPPSSIISS
  11.        ##iinncclluuddee <<ssyyss//ttyyppeess..hh>>
  12.        ##iinncclluuddee <<ddbb..hh>>
  13.  
  14. DDEESSCCRRIIPPTTIIOONN
  15.        The  routine  _d_b_o_p_e_n  is the library interface to database
  16.        files.  One of the supported file formats is btree  files.
  17.        The  general description of the database access methods is
  18.        in _d_b_o_p_e_n(3), this manual page describes  only  the  btree
  19.        specific information.
  20.  
  21.        The btree data structure is a sorted, balanced tree struc-
  22.        ture storing associated key/data pairs.
  23.  
  24.        The btree access method specific data  structure  provided
  25.        to  _d_b_o_p_e_n  is  defined in the <db.h> include file as fol-
  26.        lows:
  27.  
  28.        typedef struct {
  29.               u_long flags;
  30.               u_int cachesize;
  31.               int maxkeypage;
  32.               int minkeypage;
  33.               u_int psize;
  34.               int (*compare)(const DBT *key1, const DBT *key2);
  35.               size_t (*prefix)(const DBT *key1, const DBT *key2);
  36.               int lorder;
  37.        } BTREEINFO;
  38.  
  39.        The elements of this structure are as follows:
  40.  
  41.        flags  The  flag  value  is specified by _o_r'ing any of the
  42.               following values:
  43.  
  44.               R_DUP  Permit duplicate keys in the tree, i.e. per-
  45.                      mit  insertion  if  the  key  to be inserted
  46.                      already exists in  the  tree.   The  default
  47.                      behavior,  as  described in _d_b_o_p_e_n(3), is to
  48.                      overwrite a matching key  when  inserting  a
  49.                      new key or to fail if the R_NOOVERWRITE flag
  50.                      is specified.  The R_DUP flag is  overridden
  51.                      by   the  R_NOOVERWRITE  flag,  and  if  the
  52.                      R_NOOVERWRITE flag is specified, attempts to
  53.                      insert  duplicate  keys  into  the tree will
  54.                      fail.
  55.  
  56.                      If the database contains duplicate keys, the
  57.                      order  of  retrieval  of  key/data  pairs is
  58.                      undefined if the _g_e_t routine is  used,  how-
  59.                      ever,  _s_e_q  routine  calls with the R_CURSOR
  60.                      flag set  will  always  return  the  logical
  61.  
  62.  
  63.  
  64.                         February 21, 1994                       1
  65.  
  66.  
  67.  
  68.  
  69.  
  70. BTREE(3)                                                 BTREE(3)
  71.  
  72.  
  73.                      ``first'' of any group of duplicate keys.
  74.  
  75.        cachesize
  76.               A  suggested  maximum size (in bytes) of the memory
  77.               cache.  This value is oonnllyy advisory, and the access
  78.               method  will allocate more memory rather than fail.
  79.               Since every search examines the root  page  of  the
  80.               tree, caching the most recently used pages substan-
  81.               tially improves access time.  In addition, physical
  82.               writes are delayed as long as possible, so a moder-
  83.               ate cache can reduce the number of  I/O  operations
  84.               significantly.   Obviously, using a cache increases
  85.               (but only increases) the likelihood  of  corruption
  86.               or  lost data if the system crashes while a tree is
  87.               being modified.  If _c_a_c_h_e_s_i_z_e  is  0  (no  size  is
  88.               specified) a default cache is used.
  89.  
  90.        maxkeypage
  91.               The  maximum number of keys which will be stored on
  92.               any single page.  Not currently implemented.
  93.  
  94.        minkeypage
  95.               The minimum number of keys which will be stored  on
  96.               any  single  page.  This value is used to determine
  97.               which keys will be stored on overflow  pages,  i.e.
  98.               if  a  key or data item is longer than the pagesize
  99.               divided by the minkeypage value, it will be  stored
  100.               on  overflow  pages  instead of in the page itself.
  101.               If _m_i_n_k_e_y_p_a_g_e is 0 (no minimum number  of  keys  is
  102.               specified) a value of 2 is used.
  103.  
  104.        psize  Page  size is the size (in bytes) of the pages used
  105.               for nodes in the tree.  The minimum  page  size  is
  106.               512  bytes  and  the  maximum page size is 64K.  If
  107.               _p_s_i_z_e is 0 (no page size is specified) a page  size
  108.               is  chosen  based on the underlying file system I/O
  109.               block size.
  110.  
  111.        compare
  112.               Compare is the key comparison  function.   It  must
  113.               return  an  integer less than, equal to, or greater
  114.               than zero if the first key argument  is  considered
  115.               to  be respectively less than, equal to, or greater
  116.               than the second key argument.  The same  comparison
  117.               function must be used on a given tree every time it
  118.               is opened.  If _c_o_m_p_a_r_e is NULL (no comparison func-
  119.               tion  is  specified),  the  keys are compared lexi-
  120.               cally,  with  shorter  keys  considered  less  than
  121.               longer keys.
  122.  
  123.        prefix Prefix is the prefix comparison function.  If spec-
  124.               ified, this routine must return the number of bytes
  125.               of  the  second key argument which are necessary to
  126.               determine that it is greater  than  the  first  key
  127.  
  128.  
  129.  
  130.                         February 21, 1994                       2
  131.  
  132.  
  133.  
  134.  
  135.  
  136. BTREE(3)                                                 BTREE(3)
  137.  
  138.  
  139.               argument.   If  the  keys are equal, the key length
  140.               should be returned.  Note, the usefulness  of  this
  141.               routine  is  very data dependent, but, in some data
  142.               sets can produce significantly reduced  tree  sizes
  143.               and  search  times.   If  _p_r_e_f_i_x is NULL (no prefix
  144.               function is specified), aanndd no comparison  function
  145.               is  specified, a default lexical comparison routine
  146.               is used.  If _p_r_e_f_i_x is NULL and a  comparison  rou-
  147.               tine is specified, no prefix comparison is done.
  148.  
  149.        lorder The  byte order for integers in the stored database
  150.               metadata.  The number should represent the order as
  151.               an  integer; for example, big endian order would be
  152.               the number 4,321.  If _l_o_r_d_e_r  is  0  (no  order  is
  153.               specified) the current host order is used.
  154.  
  155.        If  the  file  already exists (and the O_TRUNC flag is not
  156.        specified), the values specified for the parameters flags,
  157.        lorder  and  psize are ignored in favor of the values used
  158.        when the tree was created.
  159.  
  160.        Forward sequential scans of a tree are from the least  key
  161.        to the greatest.
  162.  
  163.        Space freed up by deleting key/data pairs from the tree is
  164.        never reclaimed, although it is  normally  made  available
  165.        for reuse.  This means that the btree storage structure is
  166.        grow-only.  The only  solutions  are  to  avoid  excessive
  167.        deletions,  or  to create a fresh tree periodically from a
  168.        scan of an existing one.
  169.  
  170.        Searches, insertions, and deletions in a  btree  will  all
  171.        complete  in  O  lg  base N where base is the average fill
  172.        factor.  Often, inserting ordered data into btrees results
  173.        in  a low fill factor.  This implementation has been modi-
  174.        fied to make ordered insertion the best case, resulting in
  175.        a much better than normal page fill factor.
  176.  
  177. SSEEEE AALLSSOO
  178.        _d_b_o_p_e_n(3), _h_a_s_h(3), _m_p_o_o_l(3), _r_e_c_n_o(3)
  179.  
  180.        _T_h_e  _U_b_i_q_u_i_t_o_u_s  _B_-_t_r_e_e,  Douglas Comer, ACM Comput. Surv.
  181.        11, 2 (June 1979), 121-138.
  182.  
  183.        _P_r_e_f_i_x _B_-_t_r_e_e_s, Bayer and Unterauer, ACM  Transactions  on
  184.        Database Systems, Vol. 2, 1 (March 1977), 11-26.
  185.  
  186.        _T_h_e  _A_r_t  _o_f  _C_o_m_p_u_t_e_r  _P_r_o_g_r_a_m_m_i_n_g  _V_o_l_.  _3_:  _S_o_r_t_i_n_g _a_n_d
  187.        _S_e_a_r_c_h_i_n_g, D.E. Knuth, 1968, pp 471-480.
  188.  
  189. BBUUGGSS
  190.        Only big and little endian byte order is supported.
  191.  
  192.  
  193.  
  194.  
  195.  
  196.                         February 21, 1994                       3
  197.  
  198.  
  199.